#include "stdio.h"
#include "stdlib.h"
#include "GAChromosome.h"
#include "GATetris.h"
#include "GABoard.h"
#include "time.h"
#include "assert.h"
#include "limits.h"
#include "float.h"

//#define LMS_DBG_CONST_SHAPE
//#define LMS_DBG_ON

//#define LMS_DBG_SHAPE_ORDER

#ifdef LMS_DBG_ON

int gb_bDebug = 0;
void SaveBoardData(const char* zsPathName, GABoard* pBoard)
{
	FILE* hFile = fopen(zsPathName, "w");
	int x,y;

	for(y = 0; y < pBoard->GetHeight(); y++)
	{
		fprintf(hFile, "[%d]\t", y);
		for(x = 0; x < pBoard->GetWidth(); x++)
		{
			fprintf(hFile, "%d\t", pBoard->IsPieceOn(x,y));
		}
		fprintf(hFile,"\r\n");
	}

	fclose(hFile);
}

#endif


typedef struct
{
	int nHoleNum;
	int nTotalHoleSize;
	int nMaxHoleSize;

	int nSurfaceVar;

	int nFilledLineNum;

}BOARD_STATUS;


int CheckBoardStatus_surface(GABoard* pBoard, BOARD_STATUS* pStatus)
{
	int x,y;

	//1--find surface
	for(y = 0; y < pBoard->GetHeight(); y++)
	{
		int bSurface = 0;
		for(x = 0; x < pBoard->GetWidth() && bSurface == 0; x++)
		{
			bSurface = pBoard->IsPieceOn(x, y);
		}
		if(bSurface == 1)
			break;
	}

	if(y >= pBoard->GetHeight())
	{
		pStatus->nSurfaceVar = 0;
		pStatus->nFilledLineNum = 0;
		return 0;
	}

	//2--get surface variance
	int nVar = 0;
	int nStartLine = y;
	int nLastSurfaceHeight = -10;
	for(x = 0; x < pBoard->GetWidth(); x++)
	{
		for(y = nStartLine; y < pBoard->GetHeight(); y++)
		{
			if(pBoard->IsPieceOn(x,y))
			{
				if(nLastSurfaceHeight >= -1)
				{
					nVar += abs(nLastSurfaceHeight - y + 1);
				}
				nLastSurfaceHeight = y - 1;
				break;
			}

			if(y == pBoard->GetHeight() - 1)
			{
				if(nLastSurfaceHeight >= -1)
					nVar += abs(nLastSurfaceHeight - y);
				nLastSurfaceHeight = y;

			}
		}
	}
	pStatus->nSurfaceVar = nVar;

	//3--search for filled line
	int nFilledLineCount = 0;
	for(y = nStartLine; y < pBoard->GetHeight(); y++)
	{
		int nPieceOnNum = 0;
		for(x = 0; x < pBoard->GetWidth(); x++)
		{
			if(pBoard->IsPieceOn(x,y))
			{
				nPieceOnNum ++;
			}
			else
			{
				break;
			}
		}
		nFilledLineCount += nPieceOnNum == pBoard->GetWidth();
	}
	pStatus->nFilledLineNum = nFilledLineCount;

	return 0;
}


int CheckBoardStatus_hole(GABoard* pBoard, BOARD_STATUS* pStatus)
{
	int x,y;
	int nMaxHoleSize = 0;
	int nTotalHoleSize = 0;
	int nHoleCount = 0;
	for(x = 0; x < pBoard->GetWidth(); x ++)
	{
		//1--find surface of the column
		y = 0;
		while(y < pBoard->GetHeight() && !pBoard->IsPieceOn(x,y))
		{
			y++;
		}

		//2--check hole
		int nHoleStart = -1;
		for( ; y < pBoard->GetHeight(); y++)
		{
			if( !pBoard->IsPieceOn(x,y) )
			{
				if(nHoleStart < 0)
					nHoleStart = y;
			}
			else
			{
				if(nHoleStart >= 0)
				{
					int nSize = y - nHoleStart;
					nTotalHoleSize += nSize;
					nHoleCount ++;
					if(nSize > nMaxHoleSize)
						nMaxHoleSize = nSize;
					nHoleStart = -1;
				}
			}
		}

		if(!pBoard->IsPieceOn(x, y - 1) && nHoleStart >= 0)
		{
			int nSize = y - nHoleStart;
			nTotalHoleSize += nSize;
			nHoleCount ++;
			if(nSize > nMaxHoleSize)
				nMaxHoleSize = nSize;
		}

	}

	pStatus->nHoleNum = nHoleCount;
	pStatus->nMaxHoleSize = nMaxHoleSize;
	pStatus->nTotalHoleSize = nTotalHoleSize;
	return 0;

}


int CheckBoardStatus(GABoard* pBoard, BOARD_STATUS* pStatus)
{
	int ret;
#ifdef LMS_DBG_ON
	if(gb_bDebug)
		SaveBoardData("tmp/CheckStatus_IN", pBoard);
#endif
	ret = CheckBoardStatus_hole(pBoard, pStatus);
	if(ret != 0)
		return ret;

	ret = CheckBoardStatus_surface(pBoard, pStatus);
	if(ret != 0)
		return ret;
	return ret;
}

int ApplyGravity(GABoard* pBoard, GAShape* pShape, int x)
{
	int y;
	int bPlaced = 0;

	//1--get surface of this column
	for(y = 0; y < pBoard->GetHeight() && bPlaced == 0; y++)
	{
		int left = x + pShape->LeftBnd();
		int top = y + pShape->TopBnd();
		int right = x + pShape->RightBnd();
		int bottom = y + pShape->BottomBnd();

		if(left < 0 || top < 0 || right >= pBoard->GetWidth() || bottom >= pBoard->GetHeight())
			continue;

		int index;
		if(bottom == pBoard->GetHeight() - 1)
		{
			for(index = 0; index < 4; index++)
			{
				int posx = x + pShape->PieceOf(index).x;
				int posy = y + pShape->PieceOf(index).y;

				if(pBoard->IsPieceOn(posx,posy))
					break;
			}


			if(index < 4)
			{//hit one piece on 
				y --; //place the line above
				if( y + pShape->TopBnd() >= 0)
				{
					bPlaced = 1;
				}
			}
			else
			{
				bPlaced = 1;
			}

			break;
		}
		else
		{
			for(index = 0; index < 4; index++)
			{
				int posx = x + pShape->PieceOf(index).x;
				int posy = y + pShape->PieceOf(index).y;

				if(pBoard->IsPieceOn(posx,posy))
					break;
			}

			if(index < 4)
			{//hit one piece on 
				y --; //place the line above
				if( y + pShape->TopBnd() >= 0)
				{
					bPlaced = 1;
				}
				break;
			}



		}
	}
	return bPlaced == 1? y : -1;
}

int PlaceShape(GABoard* pBoard, GAShape* pShape, int x, int y)
{
	int index;
	for(index = 0; index < 4; index++)
	{
		int xpos = pShape->PieceOf(index).x + x;
		int ypos = pShape->PieceOf(index).y + y;

		if( pBoard->IsPieceOn(xpos,ypos) )
			return -1;

		pBoard->SetPiece(xpos,ypos, 0,0,0);
	}
	return 0;
}

int RemoveShape(GABoard* pBoard, GAShape* pShape, int x, int y)
{
	int index;
	for(index = 0; index < 4; index++)
	{
		int xpos = pShape->PieceOf(index).x + x;
		int ypos = pShape->PieceOf(index).y + y;

		if( !pBoard->IsPieceOn(xpos,ypos) )
			return -1;

		pBoard->RemovePiece(xpos,ypos, 0,0,0);
	}
	return 0;
}


float CalcStatusScore(BOARD_STATUS* pStatus, GAChromosome* pChromosome)
{
	float fMeanHoleSize = pStatus->nHoleNum == 0? 
	                0.0f:pStatus->nTotalHoleSize * 1.0f / pStatus->nHoleNum;
	float fScore = 0;

	fScore += pChromosome->Gene(0) * fMeanHoleSize;
	fScore += pChromosome->Gene(1) * pStatus->nFilledLineNum;
	fScore += pChromosome->Gene(2) * pStatus->nMaxHoleSize;
	fScore += pChromosome->Gene(3) * pStatus->nSurfaceVar;

	return fScore;

}


int PlayTetris(GABoard* pBoard, GAChromosome* pPlayer)
{
	int nRound = 0;
	int nShapeCost = 0;
	int bQuit = 0;
	int nTotalLineRemoved = 0;

	pBoard->Clear();

#ifdef LMS_DBG_SHAPE_ORDER
	int nTypeInOrder = 0;
#endif
	do
	{
		//1--get a shape
	    SHAPE_TYPE nType = (SHAPE_TYPE)( (rand() % TYPE_COUNT) + 1 );	

#ifdef LMS_DBG_SHAPE_ORDER
		nTypeInOrder ++;
		if(nTypeInOrder == 8) nTypeInOrder = 1;
		nType = (SHAPE_TYPE)nTypeInOrder;
#endif

#ifdef LMS_DBG_CONST_SHAPE
		nType = SHAPE_Z;
#endif
		GAShape * pShape = new GAShape(nType, 0,0,0);
		int iAngle,x,y;
		int nBestAngle = -1, nBestX = -1, nBestY = -1;
		float fTopScore = -FLT_MAX;

		for(iAngle = 0; iAngle < 4; iAngle++)
		{
			BOARD_STATUS stStatus;
			pShape->TurnRight();
             
			for(x = 0; x < pBoard->GetWidth(); x++)
			{
				int y = ApplyGravity(pBoard, pShape, x);
				if(y < 0)
					continue;

				if(PlaceShape(pBoard, pShape, x, y) != 0)
				{
					continue; //sth goes wrong
				}

				if(CheckBoardStatus(pBoard, &stStatus) != 0)
				{
					RemoveShape(pBoard, pShape, x, y);
					continue;
				}

				float fScore = CalcStatusScore(&stStatus, pPlayer);
			//	printf("\t\tAngle %d x %d y %d score %f\r\n", iAngle, x, y, fScore);
				if(fScore > fTopScore)
				{
					fTopScore = fScore;
					nBestAngle = iAngle;
					nBestX = x;
					nBestY = y;
				}


#ifdef LMS_DBG_ON
			if(gb_bDebug)
			{
				char zsFile[256];
				sprintf(zsFile, "tmp/Placed-%f", fScore);
				SaveBoardData(zsFile, pBoard);
			}
#endif
				RemoveShape(pBoard, pShape, x, y);

			}
		}

		
		if(nBestAngle >= 0)
		{
		//	printf("Placed shape %d, type %d\r\n", nShapeCost,(int)( pShape->GetShapeType()));
			for(iAngle = 0; iAngle <= nBestAngle; iAngle++)
			{
				pShape->TurnRight();
			}
			int ret = PlaceShape(pBoard, pShape, nBestX, nBestY);
			assert(ret == 0);

#ifdef LMS_DBG_ON
			if(gb_bDebug)
			{
				char zsSavedPath[234];
				sprintf(zsSavedPath, "tmp/Step_%d_IN.txt", nShapeCost + 1);
				SaveBoardData(zsSavedPath, pBoard);
			}
#endif

			nTotalLineRemoved += pBoard->ApplyGravity();

#ifdef LMS_DBG_ON
			if(gb_bDebug)
			{
				char zsSavedPath[234];
				sprintf(zsSavedPath, "tmp/Step_%d_OUT.txt", nShapeCost + 1);
				SaveBoardData(zsSavedPath, pBoard);
			}
#endif

			nShapeCost ++;
		}
		else
		{
			bQuit = 1;
		}

		delete pShape;

		nRound ++;

	}while(!bQuit);

#ifdef LMS_DBG_ON

	if(gb_bDebug)
		SaveBoardData("tmp/Quit", pBoard);
#endif

	return nTotalLineRemoved;
}

void SwitchChromosomeInfo(GAChromosome* pFst, GAChromosome* pSec)
{
	int index;
	for(index = 0;  index < pFst->GetGeneCount(); index++)
	{
		int tmp = pFst->Gene(index);
		pFst->Gene(index) = pSec->Gene(index);
		pSec->Gene(index) = tmp;
	}

	float fTmp = pFst->Score();
	pFst->Score() = pSec->Score();
	pSec->Score() = fTmp;


	unsigned long nTmp = pFst->GetUniqueID();
	pFst->SetUniqueID(pSec->GetUniqueID());
	pSec->SetUniqueID(nTmp);
	return;

}

int SortChromosome(GAChromosome* pChromosomePool, int nPoolSize)
{
	int index = 0;

#ifdef LMS_DBG_ON
	
	if(gb_bDebug)
	{
		FILE* hLog = fopen("tmp/SortIn.txt","w");

		for(index = 0; index < nPoolSize; index++)
		{
			GAChromosome* pOne = pChromosomePool + index;
			fprintf(hLog, "ID = %d\tScore = %.1f", pOne->GetUniqueID(), pOne->Score());
			int k;
			for(k = 0; k < pOne->GetGeneCount(); k++)
			{
				fprintf(hLog, "\t%d", pOne->Gene(k));
			}
			fprintf(hLog, "\r\n");

		}
		fclose(hLog);
	}
#endif

	for(index = 0; index < nPoolSize; index++)
	{
		GAChromosome* pCurrentBest = pChromosomePool + index;

		int k;
		for(k = index + 1; k < nPoolSize; k++)
		{
			GAChromosome* pOne = pChromosomePool + k;

			if(pOne->Score() > pCurrentBest->Score())
			{
				pCurrentBest = pOne;
			}
		}

		if(pCurrentBest != pChromosomePool + index)
		{
			SwitchChromosomeInfo(pCurrentBest, pChromosomePool + index);
		}

	}

#ifdef LMS_DBG_ON

	if(gb_bDebug)
	{
		FILE* hLog = fopen("tmp/SortOut.txt","w");

		for(index = 0; index < nPoolSize; index++)
		{
			GAChromosome* pOne = pChromosomePool + index;
			fprintf(hLog, "ID = %d\tScore = %.1f", pOne->GetUniqueID(), pOne->Score());
			int k;
			for(k = 0; k < pOne->GetGeneCount(); k++)
			{
				fprintf(hLog, "\t%d", pOne->Gene(k));
			}
			fprintf(hLog, "\r\n");

		}
		fclose(hLog);
	}
#endif


	return 0;

}


int main(int nargc, char* argv[])
{
	int nMaxGenerationCount = 2000;
	int nChromosomePoolSize = 200;
	int nBoardW = 20, nBoardH = 40;
	int nGeneNum = 4;

	float fTopScore = 0.0;

	int index,iGeneration;
	int x,y;

	if(nChromosomePoolSize < 4)
		return 0;

	nChromosomePoolSize = nChromosomePoolSize - (nChromosomePoolSize & 4); 
	//1--initialization
	//1.1--initialize chromosome pool
	srand(time(NULL));
	GAChromosome* pChromosomePool = new GAChromosome[nChromosomePoolSize];
	assert(pChromosomePool != NULL);
	for(index = 0; index < nChromosomePoolSize; index++)
	{
		int iGene;
		GAChromosome* pOne = pChromosomePool + index;
		pOne->SetUniqueID(index + 1);
		pOne->SetGeneCount(nGeneNum);
	
		for(iGene = 0; iGene < nGeneNum; iGene ++)
		{
			pOne->Gene(iGene) = rand() % 100 + 1;
			if(iGene != 1)
				pOne->Gene(iGene) *= -1;
		}
	}
	//1.2--initial tetris board
	GABoard* pBoard = new GABoard(nBoardW, nBoardH);
	assert(pBoard != NULL);

    //2-run GA
	for(iGeneration = 0; iGeneration < nMaxGenerationCount; iGeneration++)
	{
		printf("Generation %d/%d\r\n", iGeneration, nMaxGenerationCount);
		//2.1 play game with each chromosome
		for(index = 0; index < nChromosomePoolSize; index++)
		{
			GAChromosome* pPlayer = pChromosomePool + index;
			int nRound = 1;
			int iRound;
			pPlayer->Score() = 0;
			for(iRound = 0; iRound < nRound; iRound++)
			{
				pPlayer->Score() += PlayTetris(pBoard, pPlayer);
			}

			pPlayer->Score() /= nRound;
		}

		//2.2 sort 
		SortChromosome(pChromosomePool, nChromosomePoolSize);
		printf("\tBest Score %.2f\r\n", pChromosomePool->Score());

		if(pChromosomePool->Score() > fTopScore)
		{
			fTopScore = pChromosomePool->Score();
		    char zsSavedPath[250];
		    sprintf(zsSavedPath, "GA/%.2f.txt", fTopScore );
		    FILE* hFile = fopen(zsSavedPath, "w");
		    if(hFile != NULL)
		    {
			   for(index = 0; index < nChromosomePoolSize; index++)
			   {
				   GAChromosome* pOne = pChromosomePool + index;
				   SaveChromosome(hFile, pOne);
			   }
			   fclose(hFile);
		   }
		}

		//2.2 remove bad chromosome and run cross over to generate children
		GAChromosome* pNews = pChromosomePool + nChromosomePoolSize / 2;
		for(index = 0; index < nChromosomePoolSize / 2; index += 2)
		{
			GAChromosome* pParentA = pChromosomePool + index;
			int nParentB = index;
			while(nParentB == index)
			{
				nParentB = rand() % (nChromosomePoolSize / 2);
			}
			GAChromosome* pParentB = pChromosomePool + nParentB;
			GAChromosome* pChildA = pNews + index;
			GAChromosome* pChildB = pNews + index + 1;

			GACrossOver(pParentA, pParentB, pChildA, pChildB, 1);
		}
		//2.3-bring in some change in gene
		for(index = nChromosomePoolSize/2; index < nChromosomePoolSize; index++)
		{
			if((rand() % 100) < 40)
			{
				GAChromosome* pOne = pChromosomePool + index;
				float fFactor = (rand() % 10 - 5);
				fFactor = fFactor * 0.1 + 1;
				GAScale(pOne,fFactor);
			}
		}

		//2.4--mutation
		for(index = nChromosomePoolSize/2; index < nChromosomePoolSize; index++)
		{
			GAChromosome* pOne = pChromosomePool + index;
			GAMutation(pOne,1);
		}


	}
	

	delete pBoard;
	delete[] pChromosomePool;
	return 0;
}

